1. Field of the Invention
This invention relates to the field of information networks, and more particularly relates to a protocol for maintaining information regarding routes over a network.
2. Description of the Related Art
Generally, a router in a network uses routing tables to lookup a destination address to compute network routing and forward an incoming packet. Routing tables typically store millions of destination addresses for network hosts. Routing tables are periodically updated to reflect the active status of hosts in the network. When a packet arrives at a router, the router extracts the destination information from packet header and searches the routing table for the destination route. Because the routing tables are based on conventional memory technology and contain a large amount of routing information, a search for the destination route can take significant amount of time and in some cases, may cause the router to drop the incoming packet due to certain timeout limits.
One method to resolve route lookup delay is to implement a route cache. Typically, a route cache is a software-based search table. A route cache is a comparatively smaller lookup table that stores the addresses of certain selected destinations (e.g., most frequently accessed destinations, recently accessed destinations and the like). When the router receives a packet, the router first searches the route cache for routing information and if the routing information is found in the route cache, the router forwards the packet to the appropriate destination. Because the route cache is smaller, the search time is significantly less than the search time of larger lookup tables. The route cache is populated based on statistical and data traffic analysis done by each router in the network. A problem with software-based route caches is that the router keeps adding destination addresses to the route cache until the length of route cache reaches a certain maximum limit and the search efficiency starts degrading router's performance. The router then flushes the route cache (clears all the entries in the cache) and repopulates the route cache. The flushing and repopulating of the route cache causes additional delays for packet routing. This additional delay severely affects router performance and limits the maximum allowable throughput of the router.
One solution to this situation is the use of a hardware-based route cache. By storing the most frequently-used routing information in hardware, access to this information is hastened considerably. However, in this scenario, as with any caching scenario, a choice must be made as to which entries from the software-based routing tables to load into the hardware-based cache. As is known, least-recently used (LRU) techniques can provide good performance and relatively simple implementation to the question of page replacement. Of course, if all the page requests are known in advance, the best strategy is to evict that item whose next request occurs furthest in the future. This strategy is known as the MIN algorithm. Typically, it is not possible to know future requests. Techniques that assume no knowledge of future requests and base their decisions only on past requests are called online algorithms, of which the LRU technique is one. LRU works by replacing that page in the cache whose most recent request occurred furthest in the past, which is referred to as the oldest page. Heuristically, LRU's strategy is based on the assumption that the probability a given page will be accessed in the future is proportional to how recently that page was accessed for the last time in the past.
What is therefore needed is method and apparatus that allows for large routing tables through the use of a hardware cache, that do not experience the delays associated with software-based routing caches and the software control associated with such software-based routing caches.